/**
 * @file   Heap.h
 * @author Crazyfish <wangheyu@zju.edu.cn>
 * @date   Wed Aug 26 15:53:41 2020
 * 
 * @brief  An implementation of heap. 
 * 
 * 
 */

#ifndef __CRAZYSIGH_HEAP__
#define __CRAZYSIGH_HEAP__

class Heap
{
private:
     int *data;			/**< Store data of heap. */
     int length;		/**< Number of the elements in the heap. */

public:
#define PARENT(i) ((((i) + 1) >> 1) - 1)
#define LEFTCHILD(i) (((i + 1) << 1) - 1)
#define RIGHTCHILD(i) ((i + 1) << 1)
     
     /** 
      * Default constructor.
      * 
      */
     Heap();

     /** 
      * Constructor, initialize data with a bunch of elements pointed by 
      * datahead. 
      * 
      * @param datahead Pointer to the elements data.
      * @param l Total number of the elements data. 
      */
     Heap(int *datahead, int l);

     /** 
      * Default destructor.
      * 
      */
     ~Heap();

     /** 
      * Rebuild the heap. If the old one is not empty, all data will BE DESTROYED.
      * 
      * @param datahead Pointer to the elements data.
      * @param l Total number of the elements data.
      * 
      * @return Error code, 0 for OK. 
      */
     int rebuild(int *datahead, int l);

     /** 
      * Get the length of the heap.
      * 
      * 
      * @return The length of the heap.
      */
     int get_length();

     /** 
      * Get the height of the heap.
      * 
      * 
      * @return The height of the heap.
      */
     int get_height();

     /** 
      * Check if the heap has no data element.
      * 
      * 
      * @return Ture for empty. 
      */
     bool is_empty();

     /** 
      * Get the index of parent node.
      * 
      * @param i The index of the current node.
      * 
      * @return The index of the parent node.
      */
     int parent(int i);

     /** 
      * Get the index of the left child node.
      * 
      * @param i The index of the current node.
      * 
      * @return The index of the left child node.
      */
     int left_child(int i);

     /** 
      * Get the index of the right child node.
      * 
      * @param i The index of the current node.
      * 
      * @return The index of the right child node.
      */
     int right_child(int i);

     /** 
      * Shift down the i-th node to recover the properties of min-heap.
      * 
      * @param i The index of the broken node.
      * 
      * @return Error code, 0 for OK.
      */
     int shiftdown(int i);

     /** 
      * Print out all elements.
      * 
      * 
      * @return Error code, 0 for OK.
      */
     int printout();

     /** 
      * Sort all the elements by heap-sort method.
      * 
      * 
      * @return Error code, 0 for OK.
      */
     int sort();
};

#else
// Do nothing.
#endif
